카탈랑 수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
4. 조합론적 의미
5. 역사
6. 일반화
7. 행렬 표현
- 7.1. 한켈 행렬
참조

1. 개요

카탈랑 수는 조합론에서 나타나는 수열로, 음이 아닌 정수 n에 대해 여러 가지 방법으로 정의된다. 카탈랑 수는 이항 계수를 사용하여 표현하거나, 점화식 또는 생성 함수를 통해 정의할 수 있으며, 여러 조합론적 문제의 해로 나타난다. 예를 들어, 괄호를 올바르게 묶는 방법의 수, 이진 트리의 개수, 격자 경로의 수 등이 카탈랑 수와 관련된다. 카탈랑 수는 홀수 또는 짝수이며, 점근적으로 증가하며, 행렬 표현이 가능하다.

더 읽어볼만한 페이지

열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 $\{1,2,\ldots,n\}$ 의 순열에서 $a_i>a_{i+1}$ 인 $i$ 가 정확히 $m$ 개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.
열거조합론 - 형식적 멱급수
형식적 멱급수는 환의 원소를 계수로 갖는 무한 차수 다항식의 집합으로, 덧셈과 곱셈 연산을 통해 환의 구조를 이루며 미분, 합성 등의 연산이 정의되고, 점화식 풀이 등 다양한 분야에 응용된다.
정수열 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.
정수열 - 소수 (수론)
소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이며, 무한히 많고 정수론의 기본 정리에서 중요한 역할을 하며 다양한 분야에 응용된다.

카탈랑 수

2. 정의

카탈랑 수 $C \colon \mathbb N \to \mathbb N$

: $C \colon n \mapsto C_n$ 는 여러 방법으로 정의될 수 있는 자연수열이며, 이 정의들은 모두 서로 동치이다.

''n''이 충분히 클 때, 카탈랑 수는 다음 식으로 근사할 수 있다(이는 월리스 공식으로부터 증명할 수 있다).

: $C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.$

$n=2^k-1$ (메르센 수)일 때에만 $C_n$ 은 홀수가 되며, 그 외의 경우 $C_n$ 는 짝수가 된다.

2. 1. 직접적 정의

음이 아닌 정수 ''n''에 대하여, ''n''번째 카탈랑 수

C_n

는 다음과 같이 정의된다.

:

C_n = \frac1{n+1}\binom{2n}n = \frac{(2n)!}{n!(n+1)!} = \prod_{i=2}^n\frac{n+i}i

여기서

(-)!

는 계승 (수학)이며,

\textstyle\binom{-}{-}

은 이항 계수이다.

카탈랑 수는 다음과 같이도 표현할 수 있다.

:

C_n = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1

2. 2. 점화식

카탈랑 수는 다음과 같은 점화식으로 재귀적으로 정의될 수 있다.^[9]

:

C_0 = 1

:

C_{n+1}=\sum_{i=0}^n C_i C_{n-i} = C_0C_n+C_1C_{n-1}+\dotsb+C_nC_0\qquad(n\ge0)

또한, 다음과 같은 점화식을 사용할 수도 있다.

:

C_0 = 1

:

C_{n+1} = \frac{2(2n+1)}{n+2}C_n

위의 두 점화식은 아래와 같이 나타낼 수도 있다.

:

\begin{align}C_0 &=1, \quad C_1 =1, \\C_{n+1} &=\frac{2(2n+1)}{n+2} \, C_n = \sum_{i=0}^n C_i \, C_{n-i} = C_0 \, C_n + C_1 \, C_{n-1} + C_2 \, C_{n-2} +\cdots +C_n \, C_0\end{align}

2. 3. 생성 함수

카탈랑 수의 생성 함수는 다음과 같이 정의된다.

:

c(x)=\sum_{n=0}^\infty C_n x^n.

이는 다음과 같은 관계를 만족한다.

:

c(x)=1+xc(x)^2.

이 식은 양변을 멱급수로 전개하여 점화 관계로부터 유도할 수 있다. 점화 관계는 카탈랑 수를 고유하게 결정한다. 위 식을 이차 방정식으로 보고 근의 공식을 사용하여 풀면, 다음 두 가지 해를 얻는다.

:

c(x) = \frac{1+\sqrt{1-4x}}{2x}

또는

c(x) = \frac{1-\sqrt{1-4x}}{2x}

.

이 중 두 번째 해가

C_0 = \lim_{x \to 0} c(x) = 1

을 만족하므로 카탈랑 수의 생성 함수는 다음과 같다.

:

c(x) = \frac{1-\sqrt{1-4x}}{2x} = \sum_{n=0}^{\infty} \frac{1}{n+1} \binom{2n}{n}x^{n}\,.

3. 성질

카탈랑 수( $C_n$ )는 다음과 같이 여러 가지로 표현할 수 있다.

: $C_n = {2n\choose n} - {2n\choose n+1} = \frac{1}{2n+1} {2n+1\choose n} = {2n\choose n} - {2n\choose n-1} \quad\mbox{ for }n\ge 1$

카탈랑 수는 다음과 같은 점화식을 만족한다.^[1]

: $\begin{align}C_0 &=1, \quad C_1 =1, \\C_{n+1} &=\frac{2(2n+1)}{n+2} \, C_n = \sum_{i=0}^n C_i \, C_{n-i} = C_0 \, C_n + C_1 \, C_{n-1} + C_2 \, C_{n-2} +\cdots +C_n \, C_0\end{align}$

생성 함수는 다음과 같다.

: $\frac{1-\sqrt{1-4x}}{2x}= \sum_{n=0}^\infty {2n \choose n} \frac{x^n}{n+1}$

소수인 카탈랑 수는 $C_2 = 2$ 와 $C_3 = 5$ 뿐이다.^[1]

3. 1. 점근적 성질

''n''이 충분히 클 때, 카탈랑 수는 다음 식으로 근사할 수 있다.

:

C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}.

이는 스털링 근사 또는 월리스 공식으로 증명할 수 있다.

n = 2^k - 1

(메르센 수)일 때에만

C_n

은 홀수가 되며, 그 외의

n

에서의

C_n

는 짝수가 된다.

3. 2. 홀짝성

카탈랑 수

C_n

이 홀수인 경우는

n

이 메르센 수

n=2^k-1

일 때뿐이며, 나머지는 모두 짝수이다.^[23]

홀수인 카탈랑 수는 다음과 같다.

$C_{2^0-1} = 1$
$C_{2^1-1} = 1$
$C_{2^2-1} = 5$
$C_{2^3-1} = 429$

3. 3. 적분 표현

카탈랑 수Catalan number^영어는 다음과 같은 적분 표현을 갖는다.^[4]^[5]

:

C_n=\frac {1}{2\pi}\int_0^4 x^n\sqrt{\frac{4-x}{x}}\,dx\,=\frac{2}{\pi}4^n\int_{-1}^{1} t^{2n}\sqrt{1-t^2}\,dt.

4. 조합론적 의미

조합론에서 카탈랑 수는 여러 문제의 해답으로 등장한다. 조합 수학자 리처드 P. 스탠리의 저서 《Enumerative Combinatorics》 2권^[24]에는 카탈랑 수의 66가지 표현이 소개되어 있다.

''C''_''n''은 -1과 1 값으로 만들어진 수열 (''a''₁, ''a''₂, ..., ''a''_2''n'')에서 ''a''₁+''a''₂+...+''a''_2''n''=0 일 때, 각각의 부분합 a₁, a₁+a₂, ..., ''a''₁+''a''₂+...+''a''_2''n''이 모두 0 이상이 되도록 하는 방법의 수이다.
''C''_''n''은 ''a''_''i''가 1 또는 -1일 때, ''a''₁+''a''₂+...+''a''_2''n''+2=0이고 각각의 부분합 a₁, a₁+a₂, ..., ''a''₁+''a''₂+...+''a''_2''n''+1이 모두 0 보다 크게 되도록 하는 방법의 수이다.
''C''_''n''은 ''n'' + 1개의 항에 이항 연산을 적용하는 순서의 모든 가지수이다.
''C''_''n''은 높이 ''n''인 계단 모양을 ''n''개의 직사각형으로 타일링하는 방법의 수이다.
''C''_''n''는 수평선 위에 유지되는 ''n''개의 상승 스트로크와 ''n''개의 하강 스트로크로 "산맥"을 형성하는 방법의 수이다. (산맥은 지평선 아래로 내려가지 않는다.)
''C''_''n''는 다이어그램이 2-by-''n'' 직사각형인 표준 영 도표의 수이다.
''C''_''n''은 1로 시작하여 0 또는 1만큼 증가하거나 임의의 수(최소 1)만큼 감소할 수 있는 길이 ''n'' 시퀀스의 수이다.

4. 1. 괄호 묶기 및 이진 트리

''C''_''n''은 ''n''쌍의 괄호를 올바르게 묶는 방법의 수이다.
''C''_''n''은 ''n'' + 1개의 잎을 갖는 이진 트리의 개수이다.

''C''_''n''은 정 이진 트리 가운데 자식을 가진 노드(internal vertex, 혹은 branch라고 부르는)가 ''n''개인 트리의 개수이다. ('''정''' 이진 트리는 한 개의 자식만 가진 노드가 없고, 모든 노드가 두 개의 자식을 가졌거나 혹은 단말 노드인 트리를 가리킨다.)

4. 2. 격자 경로

''C_n''은 ''n'' × ''n'' 격자에서 대각선을 넘지 않고 왼쪽 아래에서 오른쪽 위로 가는 최단 경로의 수이다. 이러한 경로는 딕 단어를 세는 것과 동일하며, X는 "오른쪽으로 이동"을, Y는 "위로 이동"을 의미한다.^[24]

이것은 열 높이별로 카탈란 요소를 나열하여 나타낼 수 있다.^[8]

[0,0,0,0] [0,0,0,1] [0,0,0,2] [0,0,1,1]

[0,1,1,1] [0,0,1,2] [0,0,0,3] [0,1,1,2] [0,0,2,2] [0,0,1,3]

[0,0,2,3] [0,1,1,3] [0,1,2,2] [0,1,2,3]

딕 단어를 사용하여

\textstyle \binom{2n}{n}

에서 시퀀스를 시작한다.

X_d

를 초기 부분 시퀀스를 동일하게 만드는 첫 번째 X라고 하고, 시퀀스를

(F)X_d(L)

로 구성한다. 새로운 시퀀스는

LXF

이다.

카탈랑 수는 격자 모양 경로 세기로 설명 가능한데, ''C_n''은 세로, 가로 ''n''칸의 격자에서 대각선을 넘지 않고 격자점을 통과하여 마주보는 점을 최단 거리로 연결하는 경로의 총 수이다.

4. 3. 다각형 삼각 분할

''C_n''은 ''n'' + 2각형을 ''n''개의 삼각형으로 나누는 방법의 수이다. 아래 그림은 6각형을 4개의 삼각형으로 나누는 모든 방법을 나타낸 것으로 총 C₄가지이다.

^[24]

4. 4. 기타 조합론적 의미

''C''_''n''은 길이가 ''2n''인 뒥 단어의 개수이다. 뒥 단어는 n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다.^[24] 예를 들어, 길이가 6인 모든 뒥 단어는 다음과 같다.

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

''C''_''n''은 ''2n''명이 원을 이루어 손을 교차시키지 않고 악수하는 경우의 수이다.
''C''_''n''은 집합 의 비교차 분할의 수이다.

5. 역사

몽골의 수학자 명안도(c. 1692-c. 1763)가 18세기에 최초로 카탈랑 수를 발견하였다.^[25]^[26]^[27] 명안도는 제자 진계신이 1774년에 완성했지만 60년 후에 출판된 저서 《격원밀률첩해(割圓密率捷法)》[원분적률첩해]를 집필하기 시작했다. 예를 들어, 명안도는 $\sin(2 \alpha)$ 및 $\sin(4 \alpha)$ 의 급수 전개를 $\sin(\alpha)$ 의 관점에서 표현하기 위해 카탈랑 수열을 사용했다. 피터 J. 라콤(1999)은 1700년대 초에 세 개의 무한 급수를 중국에 가져온 피에르 자르투의 자극을 포함하여 명안도의 연구 특징을 개략적으로 설명했다.

명안도의 저서 ''원분적률첩해(圓分積率捷法)'' 제3권에 나타난 카탈랑 수

유럽에서는 레온하르트 오일러가 다각형을 삼각형으로 나누는 문제와 관련하여 카탈랑 수를 처음 기술했다. 벨기에의 수학자 외젠 샤를 카탈랑은 하노이의 탑 문제를 연구하면서 카탈랑 수를 재발견하고 괄호 표현과의 관계를 밝혔다.^[28]^[29] 1887년 데지레 앙드레는 뒥 단어에 대한 반사 계산 기법(두 번째 증명)을 발견하였다.

"카탈랑 수"라는 이름은 존 리오단에서 유래되었다.^[14]

6. 일반화

카탈랑 수는 베르트랑 투표 정리의 특수한 경우로 해석될 수 있다. 구체적으로, $C_n$ 은 $n+1$ 표를 가진 후보 A가 $n$ 표를 가진 후보 B를 이기는 경우의 수이다.

음이 아닌 정수의 2개 매개변수 수열 $\frac{(2m)!(2n)!}{(m+n)!m!n!}$ 은 카탈랑 수의 일반화이다. Ira Gessel은 이 수열을 '''슈퍼 카탈랑 수'''라고 불렀다.^[17] 이 수는 때때로 슈퍼 카탈랑 수라고 불리는 슈뢰더-히파르쿠스 수와 혼동되기도 한다.

$m=1$ 인 경우, 이 수는 일반적인 카탈랑 수의 두 배이다. $m=n$ 인 경우, 이 숫자들은 쉬운 조합적 설명을 갖는다. 그러나 다른 조합적 설명은 ^[17] $m=2, 3$ 및 $4$ 에 대해서만 알려져 있으며,^[18] 일반적인 조합적 해석을 찾는 것은 미해결 문제이다.

세르게이 포민과 네이선 리딩은 임의의 유한 결정학적 콕서 그룹과 관련된 일반화된 카탈랑 수를 제시했다. 이는 그룹의 완전 가환 요소의 수이다. 관련된 루트 시스템의 관점에서, 이것은 양의 루트의 포셋에서 반사슬(또는 오더 아이디얼)의 수이다. 고전적인 카탈랑 수 $C_n$ 은 $A_n$ 유형의 루트 시스템에 해당한다. 고전적인 재귀 관계가 일반화된다: 콕서 다이어그램의 카탈랑 수는 모든 최대 고유 부분 다이어그램의 카탈랑 수의 합과 같다.^[19]

7. 행렬 표현

카탈랑 수는 행켈 행렬을 통해 표현할 수 있다. (''i'', ''j'') 항목을 카탈랑 수 ''C''_{''i''+''j''−2} 또는 ''C''_{''i''+''j''−1}로 하는 ''n'' × ''n'' 행켈 행렬의 행렬식은 ''n'' 값에 관계없이 항상 1이다. 또한 2부터 시작하는 ''n'' × ''n'' 부분 행렬의 행렬식은 ''n'' + 1이 된다. 이러한 성질들을 이용하여 카탈랑 수를 정의할 수 있다.

7. 1. 한켈 행렬

(''i'', ''j'') 항목이 카탈랑 수 ''C''_{''i''+''j''−2}인 ''n'' × ''n'' 한켈 행렬의 행렬식은 ''n''의 값에 관계없이 1이다. 예를 들어, ''n'' = 4인 경우 다음과 같다.

1	1	2	5
1	2	5	14
2	5	14	42
5	14	42	132

또한, (''i'', ''j'') 항목이 카탈랑 수 ''C''_{''i''+''j''−1}로 채워지도록 인덱싱이 "이동"되어도, ''n''의 값에 관계없이 행렬식은 여전히 1이다. 예를 들어, ''n'' = 4인 경우 다음과 같다.

1	2	5	14
2	5	14	42
5	14	42	132
14	42	132	429

이 두 조건을 함께 사용하면 카탈랑 수를 고유하게 정의할 수 있다.

카탈랑-행켈 행렬의 또 다른 특징은 2에서 시작하는 ''n'' × ''n'' 부분 행렬의 행렬식이 ''n'' + 1이라는 것이다.

\det\begin{bmatrix} 2 \end{bmatrix} = 2

\det\begin{bmatrix}  2 & 5 \\5 & 14 \end{bmatrix} = 3

\det\begin{bmatrix}  2 & 5 & 14\\5 & 14 & 42\\ 14 & 42 & 132\end{bmatrix} = 4

\det\begin{bmatrix}  2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132 \\ 14 & 42 & 132 & 429 \\ 42 & 132 & 429 & 1430\end{bmatrix} = 5

참조

_[1] 논문 Parity and primality of Catalan numbers https://www.maa.org/[...]
_[2] OEIS Catalan numbers
_[3] 웹사이트 Catalan Number https://mathworld.wo[...]
_[4] 간행물 Catalan-like number sequences and Hausdorff moment sequences
_[5] 간행물 Integral Representations of the Catalan Numbers and Their Applications 2017
_[6] 문서 Dyck paths https://www.findstat[...]
_[7] 문서 Stanley p.221 example (e)
_[8] 논문 An efficient representation for solving Catalan number related problems http://www.ijpam.eu/[...]
_[9] 문서 A. de Segner, Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula. Novi commentarii academiae scientiarum Petropolitanae 7 (1758/59) 203–209.
_[10] 문서 Rukavicka Josef (2011), On Generalized Dyck Paths, Electronic Journal of Combinatorics http://www.combinato[...]
_[11] 간행물 Enumerations of ordered trees
_[12] 간행물 A problem of arrangements
_[13] 논문 The Cycle Lemma and Some Applications http://www.cs.tau.ac[...] 1990-01
_[14] arXiv Enumerative and Algebraic Combinatorics in the 1960's and 1970's
_[15] 웹사이트 The 18th century Chinese discovery of the Catalan numbers https://www.math.ucl[...]
_[16] 웹사이트 Ming Antu, the First Inventor of Catalan Numbers in the World http://en.cnki.com.c[...] 2014-06-24
_[17] arXiv The super Catalan numbers S(m, m + s) for s ≤ 4
_[18] arXiv Super-Catalan Numbers of the Third and Fourth Kind
_[19] 문서 Sergey Fomin and Nathan Reading, "Root systems and generalized associahedra", Geometric combinatorics, IAS/Park City Math. Ser. 13, American Mathematical Society, Providence, RI, 2007, pp 63–131.
_[20] 간행물 Catalan-like number sequences and Hausdorff moment sequences
_[21] 논문 Counting symmetry: classes of dissections of a convex regular polygon
_[22] 문서 ここで\\textstyle\\binom{2n}{2}は[[組合せ (数学)|Combination]]すなわち{{mvar|{{msub|2n}}C{{msub|n}}}}のことである。
_[23] 저널 인용 https://www.maa.org/[...] 2020-01-26
_[24] 서적 인용 http://www.cambridge[...]
_[25] 저널 인용 http://ms.appliedpro[...] 2013-03-04
_[26] 저널 인용
_[27] 저널 인용 http://w3.math.sinic[...] 2013-03-04
_[28] 저널 인용 http://portail.mathd[...]
_[29] MacTutor Eugène Charles Catalan 2012-09

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com